BOJ_14500_테트로미노

깊이 우선 탐색(DFS) 문제이지만, 생각할 요소가 존재하는 문제

모든 모양을 사방 탐색으로 만들어낼 수 있지만, "ㅜ" 모양은 불가능하다
그렇기 때문에 탐색 시, 1) 사방 탐색이 가능한 것 과 2) "ㅜ" 모양을 나눠서 탐색해야 한다

"ㅜ" 모양을 탐색하는 방식은 다음과 같다

1. 가운데 방향 기준으로 나머지 3개 방향을 탐색한 후 최댓값 찾기
2. 가운데 기준으로 4개 방향을 모두 탐색하고 가장 작은 수를 제거하기

따라서 반복문을 돌면서 자리마다 dfs 및 "ㅜ" 모양을 탐색하도록 하면 된다

from collections import deque  
  
dx = [-1, 1, 0, 0]  
dy = [0, 0, -1, 1]  
N, M = list(map(int, input().split()))  
max_sum = 0  
  
paper = [list(map(int, input().split())) for _ in range(N)]  
visited = [[False] * M for _ in range(N)]  
  
  
# "ㅜ"를 제외한 나머지 방향  
def dfs(x, y, sum, cnt):  
    if cnt == 4:  
        global max_sum  
        max_sum = max(max_sum, sum)  
        return  
  
    for i in range(4):  
        nx = x + dx[i]  
        ny = y + dy[i]  
  
        if nx < 0 or nx >= N or ny < 0 or ny >= M:  
            continue  
  
        if visited[nx][ny]:  
            continue  
  
        visited[nx][ny] = True  
        dfs(nx, ny, sum + paper[nx][ny], cnt + 1)  
        visited[nx][ny] = False  
  
  
def woo(x, y):  
    around_arr = []  
  
    for i in range(4):  
        nx = x + dx[i]  
        ny = y + dy[i]  
  
        if nx < 0 or nx >= N or ny < 0 or ny >= M:  
            continue  
  
        around_arr.append(paper[nx][ny])  
  
    if len(around_arr) < 3:  
        return  
  
    elif len(around_arr) > 3:  
        around_arr.sort(reverse=True)  
        around_arr.pop()  
  
    global max_sum  
    max_sum = max(max_sum, sum(around_arr) + paper[x][y])  
  
  
for i in range(N):  
    for j in range(M):  
        visited[i][j] = True  
        dfs(i, j, paper[i][j], 1)  
        visited[i][j] = False  
        woo(i, j)  
  
print(max_sum)